原始题目：剑指 Offer 55 - II. 平衡二叉树 (opens new window)

解题思路：

求左右子树的深度，如果深度差超过 $1$，则返回 $-1$ ，否则返回子树的深度。最终判断树的深度是否为 $-1$ 即可。

代码：

public boolean isBalanced(TreeNode root) {
    return depth(root) != -1;
}

private int depth(TreeNode root) {
    if(root == null) {
        return 0;
    }
    int left = depth(root.left);
    if(left == -1) {
        return -1;
    }
    int right = depth(root.right);
    if(right == -1) {
        return -1;
    }
    return Math.abs(left - right) > 1 ? -1 : Math.max(left, right) + 1;
}

复杂度分析

• 时间复杂度$O(N)$：$N$ 为树的节点数量。最差情况下，需要遍历所有的节点。
• 空间复杂度$O(N)$：最差情况下，树退化成链表，系统递归需要 $O(N)$ 的栈空间。